# -*- coding: utf-8 -*-
# Created by zhangyanqi on 2018/4/7

"""
根据前序和中序遍历结果构造二叉树

思路；
1、前序遍历的第一个节点即为根节点
2、根据根节点，在中序遍历中找出左子树和右子树，并统计左子树和右子树的个数
3、递归构建左子树和右子树
"""

class Node(object):
    """
    节点
    """

    def __init__(self, val):
        self.val = val
        self.right = None
        self.left = None

    def set_left(self, left):
        self.left = left

    def set_right(self, right):
        self.right = right


def build(pre, in_):
    if pre is not None and len(pre) > 0:
        pre_ = pre[0]
        temp = 0
        for i in in_:
            temp += 1
            if i == pre_:
                break
        # 拆分前序遍历
        s1 = slice(1, temp)
        s2 = slice(temp, len(pre))
        pre_1 = pre[s1]
        pre_2 = pre[s2]
        # 拆分中序遍历
        s3 = slice(0, temp)
        s4 = slice(temp + 1, len(in_))
        in_1 = in_[s3]
        in_2 = in_[s4]
        node = Node(pre_)
        node.set_left(build(pre_1, in_1))
        node.set_right(build(pre_2, in_2))
        return node
    return None


if __name__ == "__main__":
    pre = [1, 2, 4, 7, 3, 5, 6, 8]
    in_ = [4, 7, 2, 1, 5, 3, 8, 6]
    n = build(pre, in_)
